/**
    算法描述：完全背包不解释
    核心问题：动态转移方程
    解决所需数据结构+算法：一维数组 + 完全背包
**/
#include<iostream>
#include<cstring>
using namespace std;

int n, c, w[101] = {0}, v[101] = {0}, dp[10001];

int main () {
    cin >> c >> n;
    for (int i=1; i<=n; i++) {
    	cin >> w[i] >> v[i];
	}
    
    // core code
    memset(dp, 0, sizeof(dp));
    for (int i=1; i<=n; i++) {
        for (int j=w[i]; j<=c; j++) {
                dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }

    cout << dp[c] << endl;

    return 0;
}